package alo;

import org.junit.Test;

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @ClassName test4
 * @Description TODO
 * @Author Fanxc
 * @DATE 2021/4/15 14:37
 * @Version 1.0
 */
public class test4 {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if(k<=0||k>input.length)return list;
        Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
        for (int a :
                input) {
            if (pq.size()<k)pq.offer(a);
            else if (pq.peek()>a){
                pq.poll();
                pq.offer(a);
            }
        }
        while (!pq.isEmpty()){
            list.add(pq.poll());
        }
        return list;
    }
    public ArrayList<Integer> GetLeastNumbers_Solution2(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if(k<=0||k>input.length)return list;
        quickSearch(input,0, input.length,k,list);
        return list;
    }



    private void quickSearch(int[] nums, int lo, int hi, int k,ArrayList<Integer> list) {
        // 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数；
        int j = partition(nums, lo, hi);
        if (j == k-1||j==hi-1) {
            for (int i = 0; i < k; i++) {
                list.add(nums[i]);
            }
            return ;
        }else if (j>=k){
            quickSearch(nums, lo, j , k,list);
        }else {
            quickSearch(nums, j + 1, hi, k,list);
        }
    }
    int partition(int[] A,int low,int high) {
        int left,right,temp,pivot_item=A[low];
        left=low;
        right=high;
        while (left<right){
            while (A[left]<=pivot_item&&left<high){
                left++;
            }
            while (A[right]>pivot_item&&right>low){
                right--;
            }
            if (left<right){
                temp=A[left];
                A[left]=A[right];
                A[right]=temp;
            }
        }
        A[low]=A[right];
        A[right]=pivot_item;
        return right;
    }

    @Test
    public void test(){
        int[] a={4,5,1,6,2,7,3,8};
        GetLeastNumbers_Solution2(a,4);
    }

    class Solution {

        int partition(int [] input ,int left,int right){
            int pivot = input[left];
            while(left<right){
                while(left<right&&input[right]>=pivot)
                    right--;
                input[left]=input[right];
                while(left<right&&input[left]<=pivot)
                    left++;
                input[right]=input[left];
            }
            input[left] = pivot;
            return left;
        }

        public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
            ArrayList<Integer> list =new ArrayList();
            if(input.length==0||k>input.length)
                return list;
            int i=0,j=input.length-1;
            while(i<j){
                //切分
                int p  = partition(input,i,j);
                //当找到第k大的数，p+1==j是因为第k大的数可能在最后
                if(p==k-1||p+1==j){
                    for(int x=0;x<k;x++)
                        list.add(input[x]);
                    return list;
                }
                //当前的数在第k大的左边
                else if(p<k){
                    i=p+1;
                }
                //第k大的在当前的数的左边
                else
                    j=p;

            }
            return list;
        }
    }
}
